//如何使用js实现一个链表

// 链表是什么
// 链表是一种与数组类似的线性数据结构，然而与数组的元素存储在特定的内存位置或索引中不同，链表的每个元素都是一个单独的对象，它包含一个指向该列表中下一个对象的指针或链接
//每个元素（通常称为节点）包含两项：存储的数据和到下一个节点的链接，数据可以是任何有效的数据类型
//我们通常使用‘head’作为链表入口，这个‘head’是对链表中第一个节点的引用，而链表的最后一个节点指向null。如果是空链表，则head的引用就是null

//在 JavaScript 中，链表长这样：
const list = {
    head: {
        value: 6,
        next: {
            value: 10,                                          
            next: {
                value: 12,
                next: {
                    value: 3,
                    next: null  
                }
            }
        }
    }
}

//链表的优点：可以很容易的从链表中删除或添加节点，而无需重组整个数据结构。这是它相对于数组的一个优势
//链表的缺点： 链表的搜索操作很慢，与数组不同，不允许随机访问数据元素，必须从第一个节点开始按顺序访问节点；由于需要存储指针，相较于数组需要更多内存；



//给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
//请你将两个数相加，并以相同形式返回一个表示和的链表。
//你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class LinkedList {
    constructor(head = null){
        this.head = head
    }

    //该方法返回链表中存在的节点数：
    size() {
        let count = 0; 
        let node = this.head;
        while (node) {
            count++;
            node = node.next
        }
        return count;
    }

    //该方法清空链表
    clear() {
        this.head = null
    }

    // 该方法返回链表的最后一个节点
    getLast() {
        let lastNode = this.head;
        if (lastNode) {
            while (lastNode.next) {
                lastNode = lastNode.next
            }
        }
        return lastNode
    }

    //该方法返回链表第一个节点
    getFirst() {
        return this.head;
    }

    deleteNode(val){
        let node = this.head
        while(node){
            if(node.val === val){
                node.val = node.next.val
                node.next = node.next.next
            }
        }
    }

    //反转链表
    reverseList(nodeList){
        let p1 = nodeList.head
        let p2 = null
        while(p1){
           const temp = p1.next
           p1.next = p2
           p2 = p1
           p1 = temp
        }
        return p2
    }
}

class ListNode {
    constructor(val){
        this.val = val
        this.next = null
    }
}

var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null, carry = 0
    while(l1 || l2){
        let n1 = l1 ? l1.val : 0
        let n2 = l2 ? l2.val : 0
        let sum = n1 + n2 + carry
        if(!head){
            head = tail = new ListNode( sum % 10)
        } else {
            tail.next = new ListNode( sum % 10)
            tail = tail.next
        }

        carry = Math.floor(sum / 10)

        if(l1){
            l1 = l1.next
        }
        if(l2){
            l2 = l2.next
        }
    }

    if(carry > 0){
        tail.next = new ListNode(carry)
    }
    return head
};

let nodeList = new ListNode()
let linkList = new LinkedList(nodeList)
console.log(linkList.reverseList(list))
